The present invention relates generally to error-correcting decoding for digital signals received via noisy channels and, more particularly, to a maximum a posteriori (MAP) decoding method for turbo codes based on parallel matrix processing.
In mobile wireless communications, multipath fading, intersymbol interference and thermal noise induced by electronic devices lead to an abundance of transmission errors. Channel coding is a common method for obtaining a sufficient quality signal at a receiver. An overview of the most widespread methods for channel coding is presented by Proakis in xe2x80x9cDigital Communications,xe2x80x9d McGraw-Hill International Editions, 1989.
Recently, a novel class of binary parallel concatenated recursive systematic convolutional codes, termed turbo codes, originally described by Berrou et al. in xe2x80x9cNear Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codesxe2x80x9d, Proceedings of IEEE International Conference on Communications, 1993, pp. 1064-1070, have received a great deal of attention, see also U.S. Pat. No. 5,406,570, xe2x80x9cMethod for a maximum likelihood decoding of a convolutional code with decision weighting, and corresponding decoderxe2x80x9d issued to Berrou on Apr. 11, 1995. Turbo codes can provide excellent error correcting capability and are, therefore, very attractive for mobile wireless applications to combat channel degradation.
One of the key strategies of turbo codes is an iterative (turbo) decoding mode with soft constituent decoder information exchange, see Andersen, xe2x80x9cThe TURBO Coding Scheme,xe2x80x9d Report IT-146 ISSN 0105-854, Institute of Telecommunication, Technical University of Denmark, December 1994, and Robertson, xe2x80x9cIlluminating the Structure of Code and Decoder of Parallel Concatenated Recursive Systematic (Turbo) Codes,xe2x80x9d Proceedings of IEEE GLOBECOM Conference, 1994, pp. 1298-1303. Maximum a posteriori (MAP) based methods have proven to be the best for implementing iterative decoding of turbo codes.
A MAP method is based on the BCJR method, see Bahl et al. in xe2x80x9cOptimal Decoding of Linear Codes for Minimizing Symbol error Rate,xe2x80x9d IEEE Transactions on Information Theory, Mar. 1974, pp. 284-287). The MAP method makes optimum symbol-by-symbol decisions, and also provides soft reliability information that is necessary in iterative decoding. There is an increasing demand for practical MAP decoders so that turbo codes can be used in a wide range of applications, such as third generation wideband DS-CDMA mobile communication systems.
However, the conventional MAP method suffers serious drawbacks that make it difficult to achieve low-cost VLSI implementations. Most notably, the complex operations for forward-backward recursions required by the MAP method incur decoding delays and a substantial amount of storage. Most prior art MAP decoders require a significant complexity, compared with the convolutional-code decoders, for example, see Comatlas, Chateaubourg, France, xe2x80x9cCAS 5093 Turbo-Code Codec, data Sheet,xe2x80x9d August 1994, Efficient Channel Coding, Inc., Eastlake Ohio, USA, xe2x80x9cECC Turbo product code technology,xe2x80x9d March 1998, and Small World Communications, Adelaide, Australia, xe2x80x9cMAP04 and MAP04A 16 State MAP Decoders,xe2x80x9d April 1998.
Therefore, it is desired to provide an efficient low-complexity MAP decoder circuit and method which makes possible a practical VLSI implementation without suffering a substantial performance penalty.
The present invention provides a matrix transform method and apparatus for MAP decoding of turbo codes. In this invention, the successive decoding procedures are performed in parallel and well formulated into a set of simple and regular matrix operations. These operations substantially accelerate decoding and reduce the computational complexity, and are particularly suited for implementation in special-purpose parallel processing VLSI hardware architectures.
Using shift registers, the implementation schemes for the invented matrix MAP decoding effectively reduce the memory requirement and simplify complicated data accesses and transfers, compared with what is known in the prior art.
More particularly, the invention provides a method and apparatus for fast implementation of MAP decoding a noise corrupted turbo-encoded sequence R1N={R1, R2, . . . , RN}. In general, the method begins with initializing forward and backward recursion probability function vectors xcex10 and xcex2N by setting xcex10=[1, 0, 0, . . . , 0] and xcex2N=[1, 1, . . . , 1], respectively. Then, the method determines transition probability matrices xcex93(Rk) and xcex93i(Rk) for each received sequence Rk. Then, values of the vector xcex1k are determined according to xcex93(Rk). As xcex1k is determined, the method does multiplications on xcex93(Rk) s and xcex931(Rk).
After receiving the complete sequence R1N, an embodiment of the matrix MAP decoding method determines all values of the vector xcex2kT, k=1, 2, . . . Nxe2x88x921 in parallel by making use of the results of the above matrix multiplication on xcex93(Rk), finally the method determines the log likelihood ratios for all of decoded bits, i.e., xcex9(dk), k=1, 2, . . . N, in parallel.
An alternative embodiment directly determines the final log likelihood ratios for all of decoded bits, i.e., xcex9(dk), k=1, 2, . . . N, in parallel, by making direct use of the results of the multiplications on xcex93(Rk)s and xcex931(Rk).